#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: ugly_num.py 
@version:
@time: 2023/12/24

第n个丑数一定是由前n-1个数中的某3个丑数分别乘以2、3、5所得到的最小数，
用3个指针p2、p3、p5分别指向2、3、5应该乘以第几个丑数，
第n个丑数是由哪个指针得到的，就将其指针向后移动一位；若由多个指针得到，则对应的指针都向后移动一位。

        1 2 0 0 0 0 0 0
^
p2
p3
p5

        1 2 0 0 0 0 0 0
^       ^
p2      p2
p5

        1 2 3 0 0 0 0 0
^       ^
p5      p2
        p3

        1  2 3 4 0 0 0 0
^       ^  ^
p5      p3 p2

        1  2 3 4 5 0 0 0
        ^  ^
        p3 p2
        p5

        1  2  3 4 5 6 0 0
        ^  ^  ^
        p5 p3 p2

        1  2  3  4 5 6 8 0
        ^  ^     ^
        p5 p3    p2

        1  2  3  4 5 6 8 0
        ^     ^  ^
        p5    p3 p2
"""


def ugly_num(n):
    dp = [0] * n
    dp[0] = 1
    p2 = p3 = p5 = 0

    """
    从第二个位置开始，对dp数组中的丑数逐个进行更新，取2xdp[p2]、3xdp[p3]、5xdp[p5]中最小值为第i个丑数。
    """
    for i in range(1, n):
        dp[i] = min(2 * dp[p2], 3 * dp[p3], 5 * dp[p5])

        """
        同时更新3个指针，第n个丑数由哪个指针得到就将哪个指针向后移动一位
        最终返回第n个丑数
        时间复杂度为O(n)
        """
        if dp[i] == 2 * dp[p2]:
            p2 += 1
        if dp[i] == 3 * dp[p3]:
            p3 += 1
        if dp[i] == 5 * dp[p5]:
            p5 += 1
    return dp[-1]


print(ugly_num(5))
print(ugly_num(8))
